Subdivision surfaces have become popular recently in graphical modeling, animation, and CAD/CAM because of their stability in numerical computation, simplicity in coding, and most importantly their capability in modeling/representing complex shape of arbitrary topology. Given a control mesh and a set of mesh refining rules, a user may obtain a limit surface by recursively cutting off corners of the control mesh. The limit surface is referred to as a subdivision surface because the corner cutting/mesh refining process is a generalization of the uniform B-spline surface subdivision technique. Subdivision surfaces include uniform B-spline surfaces and piecewise Bézier surfaces as special cases. It is also known in the art that subdivision surfaces may include non-uniform B-spline surfaces and NURBS surfaces as special cases. Subdivision surfaces can model/represent complex shape of arbitrary topology because there is no limit on the shape and topology of the control mesh of a subdivision surface. It is also known that subdivision surfaces cover both parametric forms and discrete forms. Since parametric forms are useful for design and representation and discrete forms are useful for machining and tessellation (including FE mesh generation), a representation is provided which is suitable for all graphics and CAD/CAM applications.
The prior art in subdivision surfaces has focused on the areas of surface trimming, boolean operations, and mesh editing. However, there are presently few suitable methods for dealing with precision/error control in subdivision surfaces, and in “smart” tessellation of subdivision surfaces. Given a predetermined error tolerance, it is necessary to determine how many levels of recursive Catmull-Clark subdivision should be performed on the initial control mesh such that the distance between the resultant control mesh and the limit surface is less than the predetermined error tolerance. It is also desirable to improve efficiency of tessellation based applications and data communication by generating a refined mesh within the required approximation precision of the limit surface with significantly fewer faces than the uniformly refined mesh. To date, efforts to reduce the number of faces in a mesh have focused on: (1) mesh simplification, i.e. removing over-sampled vertices and producing approximate meshes with various levels of detail; (2) approximating the limit surface by known surfaces, such as displaced subdivision surface or NURBS patches; and (3) application of adaptive refinement schemes to subdivision surfaces.
Accordingly, a need is identified for an improved method for subdivision surface modeling. The subdivision depth computation technique provided by the present invention provides precision/error control tools in subdivision surface trimming, finite element mesh generation, boolean operations, and surface tessellation for rendering processes. The label-driven adaptive subdivision technique of the invention improves efficiency of the above by generating an adaptively refined mesh that is within the required approximation precision of the limit surface, but with significantly fewer quadrilateral faces than prior art uniformly refined mesh techniques. The invention provides a subdivision depth computation technique for a Catmull-Clark subdivision surface (CCSS) patch, and provides also a label-driven adaptive subdivision technique for a CCSS based on subdivision depths calculated for its patches. A novel greedy algorithm is used to eliminate illegal vertex labels in the initial mesh.
Advantageously, the methods of the present invention provide a novel and efficient error control tool which is suitable for all tessellation-based applications of subdivision surfaces, and significantly reduce the number of faces in an adaptively refined quadrilateral mesh in a few subdivision steps, thereby improving efficiency of all tessellation-based applications and data communication of subdivision surfaces.